/*
Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
Return
  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]
Note:
All words have the same length.
All words contain only lowercase alphabetic characters.
*/

class Solution {
public:
    vector<vector<string> > findLadders(string start, string end, unordered_set<string> &dict) {
        bool found = false;
        unordered_map<string, unordered_set<string>> vmap; 
        unordered_set<string> wset, wset_next, vset;
        wset.insert(start);
        while (!wset.empty() && !found) {
            vset.insert(wset.begin(), wset.end());
            for (auto word : wset) {
                bool thisfound = false;
                // generate words based on word
                for (int i = 0; i < word.length(); i++) {
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c != word[i]) {
                            string nword = word;
                            nword[i] = c;
                            if (nword == end) {
                                // found a transition path
                                found = thisfound = true; vmap[nword].insert(word);
                                break;
                            } else if (dict.find(nword) != dict.end() && vset.find(nword) == vset.end()) {
                                // found a new valid word
                                vmap[nword].insert(word); wset_next.insert(nword); 
                            }
                        }
                    }
                    if (thisfound) break;
                }
            }
            wset.clear(); swap(wset, wset_next);
        }
        vector<vector<string> > res;
        vector<string> resone(1, end);
        if (found) buildPath(start, end, vmap, resone, res);
        return res;
    }
private:
    void buildPath(string &start, string &cur, unordered_map<string, unordered_set<string>> &vmap, 
                   vector<string> &resone, vector<vector<string> > &res) {
        unordered_set<string> &strs = vmap[cur];
        for (auto word : strs) {
            resone.push_back(word);
            if (word == start) {
                res.push_back(resone); 
                reverse(res.back().begin(), res.back().end());
            } else {buildPath(start, word, vmap, resone, res); }
            resone.pop_back();
        }
    }
};
